package 算法.leetcode.offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author lchenglong
 * @date 2022/3/20
 */
public class Offer57 {

    public static void main(String[] args) {
        Offer57 instance = new Offer57();
        int[] arr = new int[]{10,26,30,31,47,60};
        int target = 40;
        int[] ans = instance.twoSum(arr, target);
        System.out.println(Arrays.toString(ans));
    }
    public int[] twoSum(int[] nums, int target) {
        // 找到比target小的数字
        int r = 0,l=0;
        for (int j=nums.length-1;j>=0;j--){
            if (nums[j]<target) {
                r = j;
                break;
            }
        }
        int[] ans = new int[2];
        while(l < r) {
            int s = nums[l] + nums[r];
            if(s < target) l++;
            else if(s > target) r--;
            else return new int[] { nums[l], nums[r] };
        }
        return ans;
    }

    public int[] twoSum2(int[] nums, int target) {
        // 最大的加最小的都比target大，所以最大的数舍弃；最小的加最大的都比target小，所以最小的舍弃
        int r = nums.length-1,l=0;
        int[] ans = new int[2];
        while(l < r) {
            int s = nums[l] + nums[r];
            if(s < target) l++;
            else if(s > target) r--;
            else return new int[] { nums[l], nums[r] };
        }
        return ans;
    }

    public int[] twoSum3(int[] nums, int target) {
// 找到比target小的数字
        int r = 0;
        for (int j=nums.length-1;j>=0;j--){
            if (nums[j]<target) {
                r = j;
                break;
            }
        }
        int[] ans = new int[2];
        Map<Integer,Integer> dic = new HashMap<Integer, Integer>();
        for (int i=0,j=r;i<j;i++,j--){
            int next = target-nums[i];
            Integer value = dic.get(next);
            if (null != value) {
                ans[0] = nums[i];
                ans[1] = next;
                break;
            } else {
                dic.put(nums[i],next);
            }
            next = target-nums[j];
            value = dic.get(next);
            if (null != value) {
                ans[0] = nums[j];
                ans[1] = next;
                break;
            } else {
                dic.put(nums[j],next);
            }
        }
        return ans;
    }
}
